//数组中出现次数超过一半的数字

//方法1：排序
//解题思路：数组排序后，如果符合条件的数存在，则一定是数组中间那个数。
//涉及到快排sort，其时间复杂度为O(NlogN)并非最优

class Solution
{
    public:
        int MoreHalfNum(vector<int> vec)
        {
            if(vec.empty())  return 0;

            sort(vec.begin(), vec.end());
            int middle = vec[vec.size()/2];

            int count = 0;
            for(int i = 0; i < vec.size(); i++)
            {
                if(middle == vec[i])  count++;
            }

            return (count > vec.size()/2) ? middle : 0;
        }
};


//方法二：众数消除
//众数：就是出现次数超过数组长度一半的那个数字
//如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数
//那么如果存在众数，最后留下的数肯定是众数

class Solution
{
    public:
        int MoreHalfNum(vector<int> vec)
        {
            if(vec.empty())  return 0;

            //遍历每一个元素，并记录次数；若与前一个元素相同，则次数加1，否则减1
            int num = vec[0];
            int count = 1;

            for(int i = 1; i < vec.size(); i++)
            {
                //次数为0 和 不为0 的情况
                if(count != 0)
                {
                    if(num == vec[i])
                        count++;
                    else 
                        count--;
                }
                else 
                {
                    //为0 重新赋值
                    num = vec[i];
                    count = 1;
                }
            }
            //判断num是否符合条件，即出现次数大于数组的一半
            count = 0;
            for(int i = 0; i < vec.size(); i++)
            {
                if(vec[i] == num)  count++;
            }

            return (count > vec.size()/2) ? num : 0;
        }
};
